

//    public class Partition {
//        public ListNode partition(ListNode pHead, int x) {
//            // write code here
//            if(pHead == null){
//                return null;
//            }
//            if(pHead.next == null){
//                return pHead;
//            }
//            ListNode newHead1 = new ListNode(0);
//            ListNode newTail1 = newHead1;
//            ListNode newHead2 = new ListNode(0);
//            ListNode newTail2 = newHead2;
//
//            while(pHead != null && pHead.next != null){
//                if(pHead.val < x){
//                    newTail1.next = pHead;
//                    newTail1 = pHead;
//                    pHead = pHead.next;
//                } else {
//                    newTail2.next = pHead;
//                    newTail2 = pHead;
//                    pHead = pHead.next;
//                }
//
//            }
//            newTail1.next = newHead2.next;
//            newTail2.next = null;
//            return newHead1.next;
//
//
//
//        }
//
//        public static void main(String[] args) {
//
//        }
//    }
//
// class ListNode {
//    int val;
//    ListNode next = null;
//
//    ListNode(int val) {
//        this.val = val;
//    }
//}
